1. Field of the Invention
The method and apparatus of the present invention relates to the rendering of lines on computer graphic display devices. More specifically, the method and apparatus of the present invention relates to the rendering of high quality lines into a low resolution frame buffer.
2. Related Applications
The present invention is related to U.S. application Ser. No. 07/413,984, filed Sep. 28, 1989 entitled "Method and Apparatus For Vector Aligned Dithering", U.S. application Ser. No. 07/413,911, filed Sep. 28, 1989 entitled "Method and Apparatus For Non-Linear Dithering of Digital Images" and U.S. application Ser. No. 07/413,983, filed Sep. 28, 1989 entitled "Method and Apparatus for Dighering Graphic Images" are herein incorporated by reference.
3. Art Background
A picture or image may be thought of as a continuous representation of the object projected. It is often desirable to represent images on a digital computer display device such as a monitor or a printer. However, a computer and its output devices are binary in nature. A computer display comprises a grid of display elements, referred to as pixels, which can either be in one of a plurality of on states indicative of its intensity, in which the pixel location is illuminated, or in the off state in which the pixel location is not illuminated. In order to display continuous images, the continuous images must be converted to discrete representations corresponding to the pixel locations on the display device. A digital image is quantized in both the spatial domain and the intensity domain.
The amount of memory available (that is, the size of the frame buffer) dictates the quantized levels available to represent the image. If the resolution of either sample space (i.e. spatial and intensity) drops below a threshold (due to memory limitations), the eye will detect the discrete boundaries between samples. In the intensity domain, insufficient resolution is marked by the presence of artificial edges delimiting the transitions between regions of incremental intensity. Other undesirable visible effects, such as patterning, color shifting and biasing, are introduced due to the visible thresholding between quantized intensity levels.
To minimize the undesirable effects, a technique, referred to as dithering or digital halftoning, is used. Dithering is a technique which permits the simulation of intensity levels between quantized levels by permitting the eye to integrate fine detail within an area and record only the overall intensity of the area. Dithering aims to sacrifice some of an image's spatial resolution for an increase in perceived intensity resolution, accomplished by averaging the intensities of several neighboring pixels to simulate intensities that lie between quantization levels. Typically, this technique works well, since the eye naturally blends individual pixel values such that only the average intensity in the surrounding area or neighborhood is perceived. For more information on dithering, see Ulichney, Digital Halftoning (1987, MIT Press); Foley & Van Dam, Fundamentals of Interactive Computer Graphics, p. 597-602 (Addison-Wesley, 1984).
Several types of dithering techniques exist. The types of dithering algorithms are distinguished by the way the neighborhoods are chosen. In the technique of ordered dither, the neighborhoods are chosen according to a two dimensional set of values, referred to as the dither table or dither matrix, which is tiled into the image's coordinate space. Typically for area dither, the table has the same number of row and column elements and the total number of entries in the table equals the number of simulatable intensity levels between the quantized levels. The values contained in the table are used to make decisions about which quantized intensity value will be output at each position, that is, should the intensity value be quantized to the quantized value above or below the original intensity value. The dither table values are different at each x,y coordinate location such that when a constant input intensity is dithered over some area, the output values will alternate in some pattern between the upper and lower quantized intensity levels.
The ordered dither process is explained in reference to FIG. 1. Process 1.0 determines the appropriate index into the dither matrix based on the x-y coordinates of the current pixel. Conceptually, the idea is to "tile" the dither matrix into the image coordinate space, thereby replicating each entry once every n pixels, where n is the dimension of the dither table. The indices to the matrix, i-j, are determined according to the following equations: EQU i=x mod n EQU j=y mod n
If n is a power of two, it is possible to utilize the least significant bits of the x-y screen coordinates for indexing the dither matrix. For example, if the dimension of the dither matrix is 4.times.4, then the 2 least significant bits of the x-y coordinates will provide the required modulo-4 indexing.
At process 2.0, the dither values are retrieved from the matrix according to i-j dither indices determined. By the nature of the problem, the output intensity scale has fewer entries than the input intensity scale. In order to quantize the input value, there must be a predetermined correspondence between each level on the output scale to a value on the input scale. It is the task of process 3.0 to determine the input-scale base value, which is the input scale value nearest to but not greater than the original input intensity and which directly corresponds to a value in the stored range of intensities.
The next process, 4.0, determines the value in the stored range of quantized intensity levels that corresponds to the input-scale base. This value will be referred to as the "stored range base value".
At process 5.0, the difference between the input intensity value and its input-scale base value is determined. The result, always guaranteed to be greater than or equal to zero, is the delta value passed along to process 6.0. Process 6.0 is the pivotal dither process, comparing the delta value to the dither value and outputting either the stored range base value or the next higher value. Specifically, if the delta value is less than or equal to the dither value, the stored range base value is output; if delta is greater than the dither value, then the stored range base plus one is output. The output from process 6.0 is the quantized pixel value that is deposited into the pixel store (e.g. a frame buffer).
Although quantized values are stored, these values are typically mapped back to an intensity scale with a greater intensity range for display viewing. That is the task of process 7.0, which is usually implemented by lookup-tables lying between the frame buffer output and the video display input. (This is not part of dithering per se, but is utilized for reconstruction of the dithered image for viewing.)
By performing processses 1.0 through 6.0 on successive input values, dithering causes values both greater than and less than the input intensity to ultimately be displayed, producing regions over which the overall average intensity is approximately equal to the original input intensity.
Because the dithering process exchanges spatial resolution for a perceived increase in bit (i.e., intensity/color) resolution, it is assumed that the object to be dithered has sufficient area to permit the resolution exchange to be accomplished. However, when dithering a line of single pixel width, very little surface area exists and as a consequence, the quality of dithered lines are reduced. Artifacts, such as disappearing line segments when the line color is close to the background color and line raggedness ("jaggies") manifest themselves in the digital image during dithering. This is illustrated in FIG. 2 which depicts a series of radial lines originating from a common central point dithered using area dither techniques. A decrease in the bit resolution (that represents the intensity values) also decreases the number of intensities available, making the image appear more ragged along its edges. In low resolution devices, these artifacts become more prevalent because the number of pixels available in any area of the digital image is small compared to the size of the image and therefore there are fewer pixels that may be used to minimize the visual effects of the artifacts by varying the intensities of the pixels.
To remove the jaggies which arise due to the under sampling of a line, anti-aliasing techniques are used. The visual effects of jaggies are decreased by smoothing the edges of the lines into the background colors by increasing the width of the line and using intermediate colors between the actual line color and the background color on the added line edge pixels. For further information on anti-aliasing, see Gupta, Sproull, "Filtering Edges for Gray Scale Displays", Computer Graphics, Vol. 15, No. 3, August, 1981.
Compositing is a technique in which a complex graphic image to be rendered can be broken down into a plurality of "sub-images" or elements which are separately rendered and subsequently blended together. However, "hot spots" often arise after anti-aliasing techniques are performed on intersecting or overlapping lines which are composited together into a single image. This is due to the addition of intensity values at the area of intersections and the nature of anti-aliased lines which typically dictates that the center of the line has a greater intensity than the edges of the lines (which are at a lower intensity in order to blend into the background color).